package leetcode_jz_offer.day12_list;

/**
 * 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的
 **/
public class Num25_合并两个排序链表 {
    private static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        //l1l2都不为空
        ListNode dummyHead=new ListNode(-1);
        ListNode last=dummyHead;
        //对链表进行尾插
        while (l1!=null&&l2!=null){
            if(l1.val<= l2.val){
                last.next=l1;
                last=l1;
                l1=l1.next;
            }else{
                last.next=l2;
                last=l2;
                l2=l2.next;
            }
            //判断l1l2是否为空
            if(l1==null){
                last.next=l2;
            }
            if(l2==null){
                last.next=l1;
            }
        }
        return dummyHead.next;
    }

    public static void main(String[] args) {
        ListNode listNode=new ListNode(1);
        ListNode listNode1=new ListNode(2);
        ListNode listNode2=new ListNode(4);
        listNode.next=listNode1;
        listNode1.next=listNode2;
        ListNode list=new ListNode(1);
        ListNode list1=new ListNode(3);
        ListNode list2=new ListNode(4);
        list.next=list1;
        list1.next=list2;
        mergeTwoLists(listNode,list);
    }
//    //递归写法
//    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//        if(l1==null){
//            return l2;
//        }
//        if(l2==null){
//            return l1;
//        }
//        //判断l1l2中val谁小，小的先拼接
//        if(l1.val<=l2.val){
//            l1.next=mergeTwoLists(l1.next,l2);
//            return l1;
//        }else{
//            l2.next=mergeTwoLists(l1,l2.next);
//            return l2;
//        }
//    }
}
